# -*- coding: utf-8 -*-

"""最大流最小割定理（Menger定理）之 Ford-Fulkerson算法"""

class FordFulk():
    def __init__(self) -> None:
        pass

    def max_flow(self, vertex, edge_f, s, t):
        """用矩阵来计算要容易些，用索引号来代表顶点"""
        path, edge_sf = [], edge_f
        def find_path(u):
            """用深度优先算法在剩余图中找到一条从u到固定点t的有效路"""
            if u == t:
                return True
            for v in range(vertex):
                if edge_sf[u][v] and (v not in path):
                    path.append(v)
                    rs = find_path(v)
                    if rs:
                        return True
                    path.pop()
            return False

        paths = []
        while True:
            path.clear()    # 初始化path
            path.append(s)

            find_path(s)    # 找一条有效路

            if len(path) == 1:    # 如果找不到一条路，就找到了在图中由s到t的最大流
                break
            # print('path:', path)

            # 计算这条路的最大流
            p, max_flow = 0, float('inf')
            while p < len(path)-1:
                if edge_sf[path[p]][path[p+1]] < max_flow:
                    max_flow = edge_sf[path[p]][path[p+1]]
                p += 1
            # print('max_flow:', max_flow)

            paths.append({'max_flow': max_flow, 'path': path.copy()})

            # 在剩余图中减路径流
            p = 0
            while p < len(path)-1:
                edge_sf[path[p]][path[p+1]] -= max_flow
                p += 1

            # 在剩余图中添加反向路径流
            p = len(path)-1
            while p > 0:
                edge_sf[path[p]][path[p-1]] += max_flow
                p -= 1
            # for x in edge_sf:
            #     print(x)

        return paths

if __name__ == '__main__':
    fordFulk = FordFulk()
    vertex, s, t = 4, 0, 2
    edge_f = [[0,10,0,20],[0,0,20,0],[0,0,0,0],[0,30,10,0]]
    paths = fordFulk.max_flow(vertex, edge_f, s, t)
    for path in paths:
        print(path)

